package datastructure.book.tujiesuanfa.backtrack._1_all;

import datastructure.book.tujiesuanfa.list.bean.ListNode;
import datastructure.book.tujiesuanfa.tree.bean.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.*;

public class Solution {
    int im = 1;
    int resultw = 0 ;

    /**
     * 由1加到target。
     * 不能使用乘除、if-else、switch-case、for 循环、while 循环，及条件判断语句等高级功能
     */
    public int mechanicalAccumulator(int target) {
        add(target);
        return resultw;
    }

    private boolean add(int target){
        resultw += im;
        return (im++ == target || add(target));
    }

    /**
     * 二维字符串数组 grid，请判断是否能在 grid 中找到目标单词 target
     * 必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用
     * 例：
     * ["A","B","C","E"]
     * ["S","F","C","S"]
     * ["A","D","E","E"]
     * ABCCEDF存在  ABCCEDFB不存在
     */
    public boolean wordPuzzle(char[][] grid, String target) {
        if (target == null || target.isEmpty()) {
            return false;
        }
        char[] charArray = target.toCharArray();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (wordPuzzle(grid, i, j, charArray, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean wordPuzzle(char[][] grid, int i, int j, char[] charArray, int m) {
        if (m > charArray.length -1){
            return true;
        }
        if (i > grid.length-1 || i < 0 || j > grid[i].length-1 || j < 0){
            return false;
        }
        if (grid[i][j] == charArray[m]) {
            grid[i][j] = '0';
            if (!wordPuzzle(grid, i, j+1, charArray, m+1)) {
                if (!wordPuzzle(grid, i, j-1, charArray, m+1)) {
                    if (!wordPuzzle(grid, i+1, j, charArray, m+1)) {
                        if (!wordPuzzle(grid, i-1, j, charArray, m+1)) {
                            grid[i][j] = charArray[m];
                            return false;
                        }
                    }
                }
            }
            return true;
        } else {
            return false;
        }
    }

    /**
     *  m x n 的二维矩阵 grid，自 grid[0][0] 开始 每次只能移动一格，
     *  不能移动到digit(i) + digit(j) > cnt  的格子中，返回可移动到的格子总数
     *  digit(x) 表示数字 x 的各数位之和，例：digit(12) = 3 、digit(2) = digit(20) = 2、digit(123) = 6
     *  例  m = 20, n = 5, cnt = 4   结果为  15
     *  m = 20, n = 5, cnt = 5   结果为  20
     *  m = 20, n = 5, cnt = 9   结果为  75
     * 0  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  10
     * 1  2  3  4  5  6  7  8  9  10 2  3  4  5  6  7  8  9  10 11
     * 2  3  4  5  6  7  8  9  10 11 3  4  5  6  7  8  9  10 11 12
     * 3  4  5  6  7  8  9  10 11 12 4  5  6  7  8  9  10 11 12 13
     * 4  5  6  7  8  9  10 11 12 13 5  6  7  8  9  10 11 12 13 14
     */
    public int wardrobeFinishing(int m, int n, int cnt) {
        int i = 0,j = 0;
        int[][] visited = new int[m][n];
        return wardrobeFinishing0(i,j,m,n,cnt,visited);
    }

    private int wardrobeFinishing0(int i, int j, int m, int n, int cnt,int[][] visited) {
        if (i >= m || j >= n) {
            return 0;
        }
        if (visited[i][j] == 1) {
            return 0;
        }
        visited[i][j] = 1;
        if (digit(i) + digit(j) > cnt) {
            return 0;
        }
        return 1+wardrobeFinishing0(i,j+1,m,n,cnt,visited)+wardrobeFinishing0(i+1,j,m,n,cnt,visited);
    }

    @Test
    public void testWardrobeFinishing(){
        System.out.println(wardrobeFinishing(20, 5, 4));
        System.out.println(wardrobeFinishing(20, 5, 5));
        System.out.println(wardrobeFinishing(20, 5, 9));
    }

    public static void main(String[] args) {
        int m = 20;int n = 5;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = digit(i) + digit(j);
                if (sum < 10) {
                    System.out.print(sum + "  ");
                } else {
                    System.out.print(sum+" ");
                }
            }
            System.out.println();
        }
    }

    private static int digit(int i){
        int sum = 0;
        while (i > 0) {
            sum += i%10;
            i/=10;
        }
        return sum;
    }

    /**
     * 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径
     *          1
     *     2          3
     *  3      1           4
     *      0      2            -4
     *  目标和为4的路径 1->2->1->0    1->3->4->-4
     */
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        LinkedList<List<Integer>> lists = new LinkedList<>();
        pathTarget0(lists,root,target,new LinkedList<Integer>());
        return lists;
    }

    private void pathTarget0(LinkedList<List<Integer>> lists, TreeNode root, int target,List<Integer> integers) {
        if (root == null) {
            return;
        }
        LinkedList<Integer> copyListLeft = new LinkedList<>();
        LinkedList<Integer> copyListRight = new LinkedList<>();
        int sum = 0;
        integers.add(root.val);
        for (Integer integer : integers) {
            sum+=integer;
            if (root.left != null){
                copyListLeft.add(integer);
            }
            if (root.right != null){
                copyListRight.add(integer);
            }
        }
        if (sum == target && root.left == null && root.right == null) {
            lists.add(integers);
        } else {
            pathTarget0(lists,root.left,target,copyListLeft);
            pathTarget0(lists,root.right,target,copyListRight);
        }
    }

    /**
     * 找出字符串的全排列
     * 例：  abc
     * abc、acb、bac、bca、cab、cba
     */
    public String[] goodsOrder(String goods) {
        char[] charArray = goods.toCharArray();
        List<String> result = new LinkedList<>();
        goodsOrder(0,charArray,result);
        return result.toArray(new String[0]);
    }

    private void goodsOrder(int startIndex,char[] charArray, List<String> result) {
        if (startIndex == charArray.length - 1) {
            result.add(new String(charArray));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = startIndex; i < charArray.length; i++) {
            if (!set.add(charArray[i])) {
                continue;
            }
            char temp = charArray[i];
            charArray[i] = charArray[startIndex];
            charArray[startIndex] = temp;
            goodsOrder(startIndex+1,charArray,result);
            temp = charArray[i];
            charArray[i] = charArray[startIndex];
            charArray[startIndex] = temp;
        }
    }
    @Test
    public void testGoodsOrder(){
        System.out.println(Arrays.toString(goodsOrder("abc")));
    }

}
